package com.gorkr.labuladong.data_struct.merge_sort;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author gorkr
 * @date 2022/05/27 00:16
 **/
public class M912_sort_an_array {

    public static int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        sort(nums,0,nums.length-1);
        return nums;
    }

    // 归并排序

    /**
     *
     * @param nums 排序数组
     * @param lo low位
     * @param hi high位
     */
    public void sort(int[] nums, int lo, int hi){
        if(lo>=hi){
            return;
        }

        int mid = (lo + hi) /2;

        sort(nums, lo, mid);
        sort(nums, mid+1, hi);
        merge(nums, lo,mid,hi);
    }

    public void merge(int[] nums, int lo, int mid, int hi){

        // 复制nums到tmp
        if (hi + 1 - lo >= 0) {
            System.arraycopy(nums, lo, tmp, lo, hi + 1 - lo);
        }

        // 数组双指针
        int i = lo, j = mid+1;
        for (int p =lo;p<=hi;p++ ){

            // 注意边界
            if (i==mid+1) {
                nums[p]=tmp[j];
                j++;
            } else if (j==hi+1) {
                nums[p]=tmp[i];
                i++;
            } else if (tmp[i]<=tmp[j]){
                nums[p]=tmp[i];
                i++;
            } else{
                nums[p]=tmp[j];
                j++;
            }
        }


    }

    @Test
    public void test(){
//        int[] nums = {5,2,3,1};
//        int[] nums = {5,1,1,2,0,0};
        int[] nums = {0};
        System.out.println(Arrays.toString(sortArray(nums)));
    }



}
    